package com.ruoxi.blog.test;

import java.util.ArrayList;
import java.util.List;

/**
	* @author YaoXian
	* @title: BinaryFind
	* @projectName ruoxi-blog
	* @description: 若兮微服务 - 二分查找
	* @date 2021-03-23 19:50
	*/
public class BinaryFind {
		
		public static void main(String[] args) {
				int [] arr = {1,8,25,25,25,25,555};
				System.out.println(binary(arr, 0, arr.length - 1, 25));
		}
		
		public static List<Integer> binary(int[] arr, int left, int right, int findVal){
				if (left>right){
						return null;
				}
				int middle = (left+right)/2;
				int middleValue = arr[middle];
				if (findVal > middleValue){
						//向右递归查找
						return binary(arr,middle+1,right,findVal);
				}else if (findVal < middleValue){
						//向左递归查找
						return binary(arr,left,middle-1,findVal);
				}else {
						int tempLeft = middle - 1;
						int tempRight = middle + 1;
						ArrayList<Integer> list = new ArrayList<Integer>();
						while (arr[tempLeft] == arr[middle]) {
								list.add(tempLeft);
								tempLeft--;
						}
						while (arr[tempRight] == arr[middle]) {
								list.add(tempRight);
								tempRight++;
						}
						list.add(middle);
						return list;
				}
				
		}
}
